/**
 * 
 */
package bitManipulation;

/**
 * @author michael
 *
 */
public class SingleNumber {

	
	
	
	/**
	Single Number
	Given an array of integers, every element appears twice except for one. Find that single one.
	
	Note:
	Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
	 */
    public int singleNumber1(int[] A) {
    	int result = 0;
        for (int i : A) {
        	result ^= i;
        }
        
        return result;
    }
    
    /**
    Single Number 2
  	Given an array of integers, every element appears three times except for one. Find that single one.

	Note:
	Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
     */
    public int singleNumber2a(int[] A) {
    	int result = 0;
    	
    	for (int offset = 0; offset <= 31; offset++) {
    		int count = 0;
    		for (int a : A) {
    			count += (a >> offset) & 0x01;
    		}
    		result = count % 3 == 0 ? result : result | (1 << offset);
    	}
    	
    	return result;
    }
 
    public int singleNumber2b(int[] A) {
    	int one = 0, two = 0, three = 0;
    	for (int i : A) {
    		two ^= one & i;
    		one ^= i;
    		three = one & two;
    		two ^= three;
    		one ^= three;
    	}
    	
    	return one;
    }
    
    
	/**
	 * 
	 */
	public SingleNumber() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
